package com.ashin.dp;

import org.junit.FixMethodOrder;
import org.junit.Test;
import org.junit.runners.MethodSorters;

import java.util.Arrays;

/**
 * 找零问题
 * <p>
 * 贪心算法的解不一定是整体最优的解
 * int[] values = {10,7,1};
 * // 总价
 * int total = 14;
 * 利用贪心得到是10 1 1 1 1
 * 其最优解为 7 7
 *
 * @Author: Ashin
 * @Date: 2020/9/16
 * @Description: com.ashin
 * @Version: 1.0.0
 */
@FixMethodOrder(MethodSorters.NAME_ASCENDING)
public class CoinChange {

    // 硬币面值
    private int[] values = {10, 7, 1};

    // 总价
    private int total = 14;

    @Test
    public void test000MinCoinCountIterator() {
        int minCoinCount = minCoinCountIterator(total, values);

        // 输出结果
        System.out.println(minCoinCount);
    }


    @Test
    public void test001MinCoinCountWithRecurise() {
        int minCoinCount = minCoinCountWithRecursion(total, values);

        // 输出结果
        System.out.println(minCoinCount);
    }

    @Test
    public void test002MinCoinCountWithRecuriseAndBacktrace() {
        int minCoinCount = minCoinCountWithGreedyRecursionAndBacktrace(total, values);
        // 输出结果
        System.out.println(minCoinCount);

        minCoinCount = minCoinCountWithRecuriseAndBacktrace(total, values);

        // 输出结果
        System.out.println(minCoinCount);
    }

    @Test
    public void test003MinCoinCountWithRecursionAndBacktraceUseMemo() {
        int[] memo = new int[total + 1];
        Arrays.fill(memo, -2);

        int minCoinCount = minCoinCountWithRecuriseAndBacktraceUseMemo(total, values, memo);

        System.out.println(minCoinCount);
    }

    @Test
    public void test004MinCoinCountWithIteratorUseMemo() {
        int minCoinCount = minCoinCountWithIteratorUseMemo(total, values);

        System.out.println(minCoinCount);
    }


    /**
     * 找零，使用迭代的方式,
     * 过于贪心，会有得不到解的问题
     *
     * @param amount 总金额
     * @param coins  币值种类,该数组必须是从大到小降序
     * @return
     */
    private int minCoinCountIterator(int amount, int[] coins) {
        //凑够total需要的币数
        int count = 0;

        // 从大到小遍历所有面值
        for (int i = 0; i < coins.length; ++i) {
            // 计算当前面值最多能用多少个
            int currentCount = amount / coins[i];
            // 计算使用完当前面值后的余额
            amount -= currentCount * coins[i];
            // 增加当前面额用量
            count += currentCount;

            if (amount == 0) {
                return count;
            }
        }

        // 如果到这里说明无法凑出总价，返回-1
        return -1;
    }

    /**
     * 找零，使用(贪心)递归的方式
     * 跟minCoinCountIterator方法一样有找不到解的问题
     *
     * @param amount 找零金额
     * @param coins  硬币币种数组，排序从大到小
     * @return 返回-1表示无法凑出金额
     * @see CoinChange#minCoinCountIterator
     */
    private int minCoinCountWithRecursion(int amount, int[] coins) {
        //如果金额小于0，或者币种数组长度为0，返回-1表示无法凑出金额amount，递归终止条件
        if (amount < 0 || coins.length == 0) {
            return -1;
        }


        // 计算当前面值最多能用多少个
        int currentCoinCount = amount / coins[0];
        // 计算使用完当前面值后的余额
        int restAmount = amount - currentCoinCount * coins[0];
        if (restAmount == 0) {
            return currentCoinCount;
        }

        //剩下的金额，用其余的币种进行求解
        int[] restCoins = Arrays.copyOfRange(coins, 1, coins.length);
        int coinCount = minCoinCountWithRecursion(restAmount, restCoins);
        if (coinCount > 0) {
            return coinCount + currentCoinCount;

        } else {
            return -1;
        }
    }


    /**
     * 针对过于贪心的问题,对代码进行改进。进行回溯，枚举所有组合，取最优值
     *
     * @param amount 金额
     * @param coins  币种数组，从大到小排序
     * @return 返回币数，如果返回-1表示无法凑够金额
     */
    private int minCoinCountWithGreedyRecursionAndBacktrace(int amount, int[] coins) {
        //如果金额小于0，或者币种数组长度为0，返回-1表示无法凑出金额amount
        if (amount < 0 || coins.length == 0) {
            return -1;
        }

        //当前币值
        int currentCoin = coins[0];

        //当前面币值使用数量
        int useCurrentCoinCount = amount / currentCoin;

        int restAmount = amount - useCurrentCoinCount * currentCoin;
        // 如果restTotal为0，表示余额已除尽，组合完成
        if (restAmount == 0) {
            return useCurrentCoinCount;
        }

        // 用于存放最少币数变量
        int minCoinCount = Integer.MAX_VALUE;
        // 其他币种数量
        int coinCount = -1;
        // 剩余的币种
        int[] restCoins = Arrays.copyOfRange(coins, 1, coins.length);
        while (useCurrentCoinCount >= 0) {
            // 递归，尝试用剩余面值数组，求当前余额的硬币总数
            coinCount = minCoinCountWithGreedyRecursionAndBacktrace(restAmount, restCoins);


            if (coinCount > 0) {
                // coinCount>0,说明有解，进行比较直接取最少的币数情况
                minCoinCount = Math.min(minCoinCount, useCurrentCoinCount + coinCount);
                // 找到一个解， 这里也可以直接结束，但是为了求解最优解，继续回溯其他组合，求解出最优的组合
                // break;
            }

            // 尝试把当前面值数-1.这里即回溯，求解下一种组合
            useCurrentCoinCount--;
            // 重新计算 restAmount
            restAmount = amount - useCurrentCoinCount * currentCoin;
        }

        if (Integer.MAX_VALUE == minCoinCount) {
            return -1;

        } else {
            return minCoinCount;
        }
    }


    /**
     * 针对过于贪心的问题,对代码进行改进。进行回溯，枚举所有组合，取最优值，和上面的区别是，上面是通过贪心的思想，能去多少取多少，无解时，通过减少币数来求解下种情况
     *
     * @param amount 金额
     * @param coins  币种数组，从大到小排序
     * @return 返回币数，如果返回-1表示无法凑够金额
     */
    private int minCoinCountWithRecuriseAndBacktrace(int amount, int[] coins) {
        // 如果余额为0，说明当前组合成立
        if (0 == amount) {
            return 0;
        }

        // 遍历所有面值
        int minCount = Integer.MAX_VALUE;
        for (int coinIdx = 0, coinLength = coins.length; coinIdx < coinLength; coinIdx++) {
            int curCoinVal = coins[coinIdx];
            // 如果当前面值大于硬币总额，那么跳过
            if (curCoinVal > amount) {
                continue;
            }

            int restAmount = amount - curCoinVal;
            // 使用当前面值，得到剩余硬币总额
            int restCount = minCoinCountWithRecuriseAndBacktrace(restAmount, coins);

            // 如果返回-1，说明组合无解，跳过
            if (restCount == -1) {
                continue;
            }

            int totalCount = 1 + restCount;
            // 保留最小总额
            if (totalCount < minCount) {
                minCount = totalCount;
            }
        }

        // 如果没有可用组合，返回-1
        if (minCount == Integer.MAX_VALUE) {
            return -1;
        }

        return minCount;
    }


    /**
     * 备忘录模式，自顶向下递归
     *
     * @param amount
     * @param coins
     * @param memo
     * @return
     */
    public int minCoinCountWithRecuriseAndBacktraceUseMemo(int amount, int[] coins, int[] memo) {
        //如果金额小于0，或者币种数组长度为0，返回-1表示无法凑出金额amount
        if (amount < 0 || coins.length == 0) {
            return -1;
        }

        //如果备忘录中已经有记录 直接返回结果
        if (memo[amount] != -2) {
            return memo[amount];
        }

        //当前币值
        int currentCoin = coins[0];

        //当前面币值使用数量
        int useCurrentCoinCount = amount / currentCoin;

        int restAmount = amount - useCurrentCoinCount * currentCoin;
        // 如果restTotal为0，表示余额已除尽，组合完成
        if (restAmount == 0) {
            return useCurrentCoinCount;
        }

        // 最少币数
        int minCoinCount = Integer.MAX_VALUE;
        // 其他币种数量
        int coinCount = -1;
        // 剩余的币种
        int[] restCoins = Arrays.copyOfRange(coins, 1, coins.length);
        while (useCurrentCoinCount >= 0) {
            // 否则尝试用剩余面值求当前余额的硬币总数
            coinCount = minCoinCountWithRecuriseAndBacktraceUseMemo(restAmount, restCoins, memo);

            // 有解直接取最少的币数
            if (coinCount > 0) {
                minCoinCount = Math.min(minCoinCount, useCurrentCoinCount + coinCount);
            }

            // 如果后续没有可用组合,退一步，当前useCurrentCoinCount币数减1 否则尝试把当前面值数-1.这里即回溯，求解下一种组合
            useCurrentCoinCount--;
            // 重新计算 restAmount
            restAmount = amount - useCurrentCoinCount * currentCoin;
        }

        if (Integer.MAX_VALUE == minCoinCount) {
            memo[amount] = -1;
            return -1;

        } else {
            memo[amount] = minCoinCount;

            return minCoinCount;
        }
    }


    /**
     * 备忘录模式，自底向上迭代
     *
     * @param amount
     * @param coins
     * @return
     */
    private int minCoinCountWithIteratorUseMemo(int amount, int[] coins) {
        // 创建备忘录
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, amount + 1);

        // 初始化状态
        memo[0] = 0;

        //someAmount 状态参数
        for (int someAmount = 1; someAmount < amount + 1; someAmount++) {
            for (int coinValue : coins) {
                if (someAmount < coinValue) {
                    continue;
                }

                // 作出决策
                memo[someAmount] = Math.min(memo[someAmount], memo[someAmount - coinValue] + 1);
            }
        }

        return memo[amount] == amount + 1 ? -1 : memo[amount];
    }


}
